/**
 * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
 * <p>
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 * 两个字符串完全匹配才算匹配成功。
 * <p>
 * 说明:
 * <p>
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
 * 示例 1:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 * 示例 2:
 * <p>
 * 输入:
 * s = "aa"
 * p = "*"
 * 输出: true
 * 解释: '*' 可以匹配任意字符串。
 * 示例 3:
 * <p>
 * 输入:
 * s = "cb"
 * p = "?a"
 * 输出: false
 * 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
 * 示例 4:
 * <p>
 * 输入:
 * s = "adceb"
 * p = "*a*b"
 * 输出: true
 * 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
 * 示例 5:
 * <p>
 * 输入:
 * s = "acdcb"
 * p = "a*c?b"
 * 输出: false
 */
class Solution {

    public static void main(String[] args) {
        /*System.out.println(isMatch("aa", "a"));//false
        System.out.println(isMatch("aa", "*"));//true
        System.out.println(isMatch("cb", "?a"));//false
        System.out.println(isMatch("adceb", "*a*b"));//true
        System.out.println(isMatch("acdcb", "a*c?b"));//false
        System.out.println(isMatch("", "*"));//true
        System.out.println(isMatch("aaabbbbbbbaababababababbababababbababababbababbaaaaaaaaaaaaaaaaaa", "a***b"));//false*/
        System.out.println(isMatch("abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaab",
                "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"));//false
    }

    /**
     * 还是用回溯的思想去做
     * 加备忘录
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        int sl = s.length();
        int pl = p.length();
        if (sl > 0 && pl > 0) {
            // 比较尾部是否一样，如果不一样，直接返回false
            char last = pChars[pl - 1];
            if (last != '*' && last != '?') {
                if (last != sChars[sl - 1]) return false;
            }
        }
        remember = new int[sl][pl];
        return isMatch(sChars, pChars, sl, pl, 0, 0);
    }

    private static int[][] remember = null;

    public static boolean isMatch(char[] sChars, char[] pChars, int sl, int pl, int x, int y) {
        if (sl < x + 1 && pl < y + 1) {
            // 如果都到了末尾
            return true;
        } else if (sl >= x + 1 && pl < y + 1) {
            // 如果p一个到了末尾
            return false;
        } else if (sl < x + 1 && pl >= y + 1) {
            // 如果s一个到了末尾
            if (pChars[y] == '*') {
                return isMatch(sChars, pChars, sl, pl, x, y + 1);
            } else {
                return false;
            }
        }
        if (remember[x][y] != 0) {
            return remember[x][y] == 1 ? true : false;
        }
        char py = pChars[y];
        if (py == '?' || py == sChars[x]) {
            boolean res = isMatch(sChars, pChars, sl, pl, x + 1, y + 1);
            remember[x][y] = res ? 1 : -1;
            return res;
        } else if (py == '*') {
            // 不管p后面是几个*，效果是一样的，所以需要优化
            int i = 1;
            for (; y + i < pl; i++) {
                if (pChars[y + i] != '*') {
                    break;
                }
            }
            boolean res = isMatch(sChars, pChars, sl, pl, x, y + i) || isMatch(sChars, pChars, sl, pl, x + 1, y) || isMatch(sChars, pChars, sl, pl, x + 1, y + i);
            remember[x][y] = res ? 1 : -1;
            return res;
        } else {
            remember[x][y] = -1;
            return false;
        }
    }


}